/**
 * 
 */
package com.gwcloud.leetcode.tags.backtrace;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName   : Leetcode401 
 * @author      : ganwei 
 * @date        : 2020年5月11日
 * @Description : Leetcode401 二进制手表
 */
public class Leetcode0401 {
	
	List<String> result = new ArrayList<>();
	int[] point_1 = {1,2,4,8,1,2,4,8,16,32};
	
	
	/**
	 * -解题思路，看到该题果断是回溯大法
	 */
    public List<String> readBinaryWatch(int num) {
    	if(num == 0){
    		result.add("0:00");
    		return result;
    	}
    	backtrack(num,0,new ArrayList<Integer>());
    	
    	return result;
    }
    
    public void backtrack(int num, int index, List<Integer> il){
    	if(il.size() == num){
    		String time = genTime(il);
    		if(!time.equals("no")){
    			result.add(time);
    		}
    		return;
    	}
    	
    	for(int i = index; i < point_1.length; i++){
    		il.add(i);
    		backtrack(num,i+1,il);
    		il.remove(il.size()-1);
    	}
    	
    }
    
    public String genTime(List<Integer> il){
    	int hour = 0;
    	int min = 0;
    	for(int i = 0; i < il.size(); i++){
    		int p = il.get(i);
    		if(p >= 0 && p <=3){
    			hour += point_1[p];
    		}
    		if(p>=4 && p <=9){
    			min += point_1[p];
    		}
    	}
    	if(hour > 11 || min > 59){
    		return "no";
    	}
    	
    	StringBuilder sb = new StringBuilder();
    	sb.append(hour);
    	sb.append(":");
    	if(min < 10){
    		sb.append("0");
    	}
    	sb.append(min);
    	
    	return sb.toString();
    }
    
    public static void main(String[] args){
    	Leetcode0401 l401 = new Leetcode0401();
    	l401.readBinaryWatch(2);
    	
    	for(String t : l401.result){
    		System.out.println(t);
    	}
    }
}
